package myalg.binaryheap;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author Pavel Belevich
 *         Date: Jul 25, 2012
 *         Time: 12:42:20 PM
 */
public class BinaryHeap<E extends Comparable<E>> {

    private List<E> h = new ArrayList<E>();

    public BinaryHeap() {
    }

    public void add(E node) {
        h.add(node);
        moveUp(h.size() - 1);
    }

    protected void moveUp(int pos) {
        while (pos > 0) {
            int parent = (pos - 1) / 2;
            if (h.get(pos).compareTo(h.get(parent)) >= 0) {
                break;
            }
            Collections.swap(h, pos, parent);
            pos = parent;
        }
    }

    public E remove() {
        E removedNode = h.get(0);
        E lastNode = h.remove(h.size() - 1);
        if (!h.isEmpty()) {
            h.set(0, lastNode);
            moveDown(0);
        }
        return removedNode;
    }

    protected void moveDown(int pos) {
        while (pos < h.size() / 2) {
            int child = 2 * pos + 1;
            if (child < h.size() - 1 && h.get(child).compareTo(h.get(child + 1)) > 0) {
                ++child;
            }
            if (h.get(pos).compareTo(h.get(child)) <= 0) {
                break;
            }
            Collections.swap(h, pos, child);
            pos = child;
        }
    }

    public static void main(String[] args) {
        BinaryHeap<Integer> heap = new BinaryHeap<Integer>();
        heap.add(2);
        heap.add(5);
        heap.add(1);

        // print elements in sorted order
        while (!heap.h.isEmpty()) {
            int x = heap.remove();
            System.out.println(x);
        }
    }

}
